#include "../8.3.1.Adjacency matrix/ljjz.c"

typedef struct edgedata
{
    int begin, end;
    int length;
} edge;

/**
 * krushal算法求最小生成树
 * @param {edge}            edges[]           边向量
 * @param {int}             left              左边界
 * @param {int}             right             右边界
 * @return void
 */
void QuickSort(edge edges[], int left, int right)
{
    edge x;
    int i, j, flag = 1;

    if (left < right)
    {
        i = left;
        j = right;
        x = edges[i];
        while (i < j)
        {
            while (i < j && edges[j].length >= x.length)
            {
                j--;
            }
            if (i < j)
            {
                edges[i++] = edges[j];
            }
            while (i < j && edges[i].length <= x.length)
            {
                i++;
            }
            if (i < j)
            {
                edges[j--] = edges[i];
            }
        }
        edges[i] = x;
        QuickSort(edges, left, i - 1);
        QuickSort(edges, i + 1, right);
    }
}

/**
 * 从图 g 的邻接矩阵读取图的所有边信息
 * @param {MGraph}          g               图的邻接矩阵存储结构
 * @param {edge}            edges[]         边向量
 * @return void
 */
void GetEdge(Mgraph g, edge edges[])
{
    int i, j, k = 0;
    for (i = 0; i < g.n; i++)
    {
        for (j = i + 1; j < g.n; j++)
        {
            if (g.edges[i][j] != 0 && g.edges[i][j] != FINITY)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].length = g.edges[i][j];
                k++;
            }
        }
    }
}

/**
 * krushal算法求最小生成树
 * @param {MGraph}          g               图的邻接矩阵存储结构
 * @return void
 */
void kruskal(Mgraph g)
{
    int i, j, k = 0, ltf1;
    int cnvx[M];
    edge edges[M * M];
    edge tree[M];
    GetEdge(g, edges);
    QuickSort(edges, 0, g.e - 1);
    for (i = 0; i < g.n; i++)
    {
        cnvx[i] = i;
    }

    for (i = 0; i < g.e; i++)
    {
        while (cnvx[edges[i].begin] != edges[i].begin)
        {
            k++;
        }

        tree[i] = edges[i];
        ltf1 = cnvx[edges[i].begin];

        for (j = 0; j < g.n; j++)
        {
            if (cnvx[j] == ltf1)
            {
                cnvx[j] = edges[i].end;
            }
        }

        k++;
    }

    printf("最小生成树的边为：\n");

    for (i = 0; i < g.n - 1; i++)
    {
        printf("\n %c --- %c %6d \n", g.vexs[tree[i].begin], g.vexs[tree[i].end], tree[j].length);
    }
}

int main() {
    Mgraph g;
    char filename[20];
    printf("请输入数据文件名：");
    gets(filename);
    creat(&g, filename,0);
    kruskal(g);
    return 0;
}